package cxydmmszl.chapter08.t145;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 容器盛水问题
 * <li style="color: green;">Desc</li>
 * 给定一个整形数组 arr，已知其中所有的值都是非负的，
 * 将这个数组看作一个容器，请返回容器能装多少水。<br/>
 * 具体请参考样例解释！
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^6<br/>
 * 1⩽arr[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N，表示数组长度。
 * 接下来一行 N 个数表示数组内的数。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示能装多少水。
 * <li style="color: blue;">Link</li> CD54
 *
 * @author habitplus
 * @since 2021-10-15 16:28
 */
public class Main {

    /*
        解题思路：
        1. 考虑 i 位置做多能装几格水，假设 i 位置左侧有数，即 arr[0, i-1]，
           i 位置右侧也有数，即 arr[i+1, arr.length-1]，
           则 i 位置上能装多少水，取决于左侧的最大值 leftMax 与右侧的最大值 rightMax，
           若 min(leftMax, rightMax) <= arr[i]，则 i 位置不能有水，
           否则 i 位置能有水的格数为：min(leftMax, rightMax) - arr[i]；
        2. 很明显，若 i 为最右侧或最左侧位置，那么该位置是不能储水的。
     */

    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException("Input is valid!");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = nextInt();

        long ans = getWaters2(arr);
        System.out.println(ans);
    }

    /*
        时间复杂度：O(N)，空间复杂度：O(N)
     */
    private static long getWaters1(int[] arr) {
        if (arr == null || arr.length < 3) return 0;

        int n = arr.length;
        int[] rightMaxs = new int[n];
        rightMaxs[n - 1] = arr[n - 1];

        for (int i = n - 2; i != -1; i--)
            rightMaxs[i] = Math.max(arr[i], rightMaxs[i + 1]);

        int leftMax = arr[0];
        long res = 0;
        for (int i = 1; i < n - 1; i++) {
            res += Math.max(Math.min(rightMaxs[i + 1], leftMax) - arr[i], 0);
            leftMax = Math.max(arr[i], leftMax);
        }
        return res;
    }

    /*
       时间复杂度：O(N)，空间复杂度：O(1)
    */
    private static long getWaters2(int[] arr) {
        if (arr == null || arr.length < 3) return 0;

        int left = 1, leftMax = arr[0];
        int right = arr.length - 2, rightMax = arr[arr.length - 1];

        long res = 0;
        while (left <= right){
            if (leftMax > rightMax) {
                // 考虑 right 位置
                res += Math.max(rightMax - arr[right], 0);
                rightMax = Math.max(arr[right--], rightMax);
            } else {
                // 考虑 left 位置 (leftMax <= rightMax)
                res += Math.max(leftMax - arr[left], 0);
                leftMax = Math.max(arr[left++], leftMax);
            }
        }

        return res;
    }
}
